package practice20;

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static int solution(int n, List<Integer> cats_levels) {
        int[] fish = new int[n];
        
        // 初始化，每只猫至少有一斤鱼干
        for (int i = 0; i < n; i++) {
            fish[i] = 1;
        }
        
        // 从左向右遍历，确保每只猫的鱼干数量不低于左边的猫
        for (int i = 1; i < n; i++) {
            if (cats_levels.get(i) > cats_levels.get(i - 1)) {
                fish[i] = fish[i - 1] + 1;
            }
        }
        
        // 从右向左遍历，确保每只猫的鱼干数量不低于右边的猫
        for (int i = n - 2; i >= 0; i--) {
            if (cats_levels.get(i) > cats_levels.get(i + 1) && fish[i] <= fish[i + 1]) {
                fish[i] = fish[i + 1] + 1;
            }
        }
        
        // 计算总共需要的鱼干数量
        int totalFish = 0;
        for (int f : fish) {
            totalFish += f;
        }
        
        return totalFish;
    }

    public static void main(String[] args) {
        List<Integer> catsLevels1 = new ArrayList<>(List.of(1, 2, 2));
        List<Integer> catsLevels2 = new ArrayList<>(List.of(6, 5, 4, 3, 2, 16));
        List<Integer> catsLevels3 = new ArrayList<>(List.of(1, 2, 2, 3, 3, 20, 1, 2, 3, 3, 2, 1, 5, 6, 6, 5, 5, 7, 7, 4));

        System.out.println(solution(3, catsLevels1)); // 应输出 4
        System.out.println(solution(6, catsLevels2)); // 应输出 17
        System.out.println(solution(20, catsLevels3)); // 应输出 35
    }
}